//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2005
//
// Merge inners in polygon object.
//

# include "StdAfx.h"
# include "Resource.h"
# include "UndoRedo.h"
# include "Status.h"
# include "MapView.h"
# include "Globals.h"

static
size_t _GetUpperPoint (const points_t & _pts) {
	size_t cUpperPoint = 0;

	const size_t cPoints = _pts.size ();
	if (cPoints == 0)
		return (size_t) -1;
	float fYmax = _pts [0].y;
	for (size_t c = 1; c < cPoints; ++ c) {
		const float fY = _pts [c].y;
		if (fY > fYmax) {
			fYmax = fY;
			cUpperPoint = c;
		} 
	}

	return cUpperPoint;
}

static
bool _IsPointInRightSide (const point_t & _x, const point_t & _a, const point_t & _0, const point_t & _b) {
	if (_a == _b)
		return true;

	const double fA = ::atan2 (_a.y - _0.y, _a.x - _0.x);

	double fBA = ::atan2 (_b.y - _0.y, _b.x - _0.x) - fA;
	if (fBA < 0)
		fBA += 2*c_PI;

	double fXA = ::atan2 (_x.y - _0.y, _x.x - _0.x) - fA;
	if (fXA < 0)
		fXA += 2*c_PI;

	return fXA <= fBA;
}

static
bool _RemoveHoles (rgn_t & _rgn, size_t _cOuter, size_t _cBeginInner, size_t _cEndInner) {
	if (_cOuter == -1)
		return false;
	if (_cBeginInner == _cEndInner)
		return false;

	assert (_cOuter < _rgn.elements.size ());
	rgn_element_t & elemOuter = _rgn.elements [_cOuter];
	if (elemOuter.points.empty ())
		return false;

	// Make sure that the outer polygon is right-oriented.
	if (! IsRightOriented (elemOuter.points))
		std::reverse (elemOuter.points.begin (), elemOuter.points.end ());

	const float c_k2 = g_map.fCosY*g_map.fCosY;

	assert (_cBeginInner < _cEndInner);
	assert (_cEndInner <= _rgn.elements.size ());

	// Count non-deleted inners.
	size_t cNonDeletedInners = 0;
	size_t cMaxTotalPoints = elemOuter.points.size ();
	for (size_t cInner = _cBeginInner; cInner < _cEndInner; ++ cInner) {
		const rgn_element_t & element = _rgn.elements [cInner];
		if (element.bDeleted)
			continue;

		++ cNonDeletedInners;

		cMaxTotalPoints += element.points.size () + 2;
	}

	bool * const pbPointsToOmit = (bool *) alloca (sizeof (bool)*cMaxTotalPoints);

	for (; cNonDeletedInners != 0; -- cNonDeletedInners) {
		//
		// Find inner element with max rectBound.y1 among non-deleted ones.
		//
		size_t cUpperInner = _cBeginInner;
		float fYmax = _rgn.rectBound.y0;
		for (size_t cInner = _cBeginInner; cInner < _cEndInner; ++ cInner) {
			const rgn_element_t & element = _rgn.elements [cInner];
			if (element.bDeleted)
				continue;

			if (element.rectBound.y1 > fYmax) {
				fYmax = element.rectBound.y1;
				cUpperInner = cInner;
			}
		}

		rgn_element_t & elemInner = _rgn.elements [cUpperInner];
		points_t & ptsInner = elemInner.points;
		const size_t cPointsInner = ptsInner.size ();

		// Make sure that the inner polygon is NOT right-oriented.
		if (IsRightOriented (ptsInner))
			std::reverse (ptsInner.begin (), ptsInner.end ());

		//
		// Get the upper point of the selected inner.
		//
		const size_t cUpperPoint = _GetUpperPoint (ptsInner);
		if (cUpperPoint == -1) {
			elemInner.bDeleted = true;
			continue;
		}
		const point_t & ptUpper = ptsInner [cUpperPoint];

		//
		const points_t & ptsOuter = elemOuter.points;
		const size_t cPointsOuter = ptsOuter.size ();

		size_t cPoint;
		for (cPoint = 0; cPoint < cPointsOuter; ++ cPoint) {
			assert (cPoint < cMaxTotalPoints);
			pbPointsToOmit [cPoint] = false;
		}

		//
		// Find the closest point of the outer element, being above the 'upper' one.
		//
		size_t cMinPoint;
		bool bStrictPass = true;
		while (true) {
			cMinPoint = 0;
			float d2_min = 2*(elemOuter.rectBound.Width ()*elemOuter.rectBound.Width () + elemOuter.rectBound.Height ()*elemOuter.rectBound.Height ());
			bool bMinPointFound = false;
			for (cPoint = 0; cPoint < cPointsOuter; ++ cPoint) {
				if (pbPointsToOmit [cPoint])
					continue;
				const point_t & p = ptsOuter [cPoint];

				if (p.y < ptUpper.y)
					continue;

				const float d2 = (p.x - ptUpper.x)*(p.x - ptUpper.x)*c_k2 + (p.y - ptUpper.y)*(p.y - ptUpper.y);
				if (d2 < d2_min) {
					d2_min = d2;
					cMinPoint = cPoint;
					bMinPointFound = true;
				}
			}

//			assert (bMinPointFound);
			if (! bMinPointFound) {
				// NOTE: Typical reason is intersections of contours.

				if (bStrictPass == false) {
					assert (false);

					// NOTE: avoid infinite loop.
					goto l_next_inner;
				}

				bStrictPass = false;
				for (cPoint = 0; cPoint < cPointsOuter; ++ cPoint) {
					assert (cPoint < cMaxTotalPoints);
					pbPointsToOmit [cPoint] = false;
				}

				continue;
			}

			const point_t & pA = ptsOuter [cMinPoint != 0                ? cMinPoint - 1 : cPointsOuter - 1];
			const point_t & p0 = ptsOuter [cMinPoint];
			const point_t & pB = ptsOuter [cMinPoint != cPointsOuter - 1 ? cMinPoint + 1 : 0];
			if (
				d2_min == 0 ||
				(
					_IsPointInRightSide (ptUpper, pA, p0, pB) &&
					(bStrictPass ? (! SegmentIntersectsPolyline (ptsOuter [cMinPoint], ptUpper, ptsOuter, true)) : true)
				)
			)
				break;

			assert (cMinPoint < cMaxTotalPoints);
			pbPointsToOmit [cMinPoint] = true;
		}

		{
			//
			// Prepare points of the joined polygon.
			//

			points_t pointsJoin (cPointsOuter + cPointsInner + 2);
			std::copy (ptsOuter.begin (), ptsOuter.begin () + cMinPoint + 1,   pointsJoin.begin ());
			size_t cFilled = cMinPoint + 1;
			std::copy (ptsInner.begin () + cUpperPoint, ptsInner.end (),       pointsJoin.begin () + cFilled);
			cFilled += cPointsInner - cUpperPoint;
			std::copy (ptsInner.begin (), ptsInner.begin () + cUpperPoint + 1, pointsJoin.begin () + cFilled);
			cFilled += cUpperPoint + 1;
			std::copy (ptsOuter.begin () + cMinPoint, ptsOuter.end (),         pointsJoin.begin () + cFilled);
			cFilled += cPointsOuter - cMinPoint;
			assert (cFilled == pointsJoin.size ());

			//
			// Annex inner into outer.
			//
			elemOuter.points.swap (pointsJoin);
		}

l_next_inner:
		elemInner.bDeleted = true;
	}

	return true;
}

void DoRemoveHoles (rgn_t & _rgn) {
	assert (_rgn.IsPolygon ());

	bool bModified = false;

	size_t cOuter = (size_t) -1;

	const size_t cElements = _rgn.elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		rgn_element_t & element = _rgn.elements [cElement];
		if (element.bDeleted)
			continue;

		if (element.bHole == false) {
			if (_RemoveHoles (_rgn, cOuter, cOuter + 1, cElement))
				bModified = true;
			cOuter = cElement;
		}
	}
	if (_RemoveHoles (_rgn, cOuter, cOuter + 1, cElements))
		bModified = true;

	if (bModified) {
		_rgn.RefreshAttributes (g_map, false);
		_rgn.dwFlags |= rgn_t::fModified;
	}
}

////////////////////////////////////////

class CRemoveHolesAction : public CEditAction {
  public:
	CRemoveHolesAction () {}

	virtual void GetName (string_t & _str) const {_str.append ("merge inner polygons");}
	virtual cu_t CanUndo () const {return cuBackup;}
	virtual bool Do ();
	virtual void Undo () {}
	virtual void Redo () {}
};

bool CRemoveHolesAction::Do () {
	CCritSec::CLock lock (g_cs);

	layer_t & polygons = g_map.layers [rkPolygon];

	const size_t cTotalRgns = polygons.cRgns;
	if (cTotalRgns == 0)
		return true;
	size_t cRgnsProcessed = 0;
	SetStatus (GetStr (IDS_STATUS_REMOVING_INNERS));
	SetProgressStatus (0);

	rgns_t & rgns = polygons.rgns;
	for (rgns_t::iterator iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
		rgn_t & rgn = * iRgn;
		if (rgn.IsDeleted () || rgn.IsWTR ())
			continue;

		DoRemoveHoles (rgn);

		++ cRgnsProcessed;
		SetProgressStatus (cRgnsProcessed*100/cTotalRgns);
	}

	SetStatusReady ();

	return true;
}

void RemoveHoles () {
	PerformEditAction (new CRemoveHolesAction ());
	Refresh ();
}
